package com.zhugang.week11;

/**
 * @program algorithms
 * @description: minDistance
 * @author: chanzhugang
 * @create: 2022/09/05 17:58
 */
public class MinDistance {

    /**
     * 72 编辑距离
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        // word1 转成word2 最少操作数
        // 操作：插入一个字符、删除一个字符、替换一个字符
        // dp[i][j] : 表示长度为i的t1子串和长度为j的t2的子串的编辑距离
        // dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1]) : t1[i - 1] = t2[j - 1]
        // dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1) : t1[i - 1] != t2[j - 1]

        int n = word1.length();
        int m = word2.length();
        if (n == 0) return m;
        if (m == 0) return n;

        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();

        // dp[i][j] : w1[0 ~ i-1] 和 w2[0 ~ j-1]的最小编辑距离
        int[][] dp = new int[n + 1][m + 1];
        // 初始化第一列、第一行
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (w1[i - 1] == w2[j - 1]) {
                    // 匹配了距离不变；不匹配+1
                    dp[i][j] = min3(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1]);
                } else {
                    dp[i][j] = min3(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[n][m];
    }

    private int min3(int a, int b, int c) {
        int minv = a;
        if (minv > b) {
            minv = b;
        }
        if (minv > c) {
            minv = c;
        }
        return minv;
    }
}